import java.lang.System;

/**
 * 找第K个最⼤的元素
 *
 * 示例 1:
 * 输⼊: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 */
public class FindKLargestElement {
    
    public int solution(int[] nums, int k) {
        k = nums.length - k;
        int l = 0, r = nums.length - 1;

        while(l < r) {
            int j = partition(nums, l, r);
            if (j == k) {
                break;
            } else if (j < k) {
                l = j + l;
            } else {
                r = j - l;
            }
        }
        return nums[k];
    }

    private int partition(int[] nums, int l, int r) {
        int i = l, j = r + l;
        int v = nums[l];
        while (true) {
            while (nums[++i] < v && i < r) ;
            while (nums[--j] > v && j > l) ;
            if(i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, l, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3,2,1,5,6,4};
        System.out.println(new FindKLargestElement().solution(nums, 2));
    }
}